1743F - Intersection and Union - CodeForces Solution

import io,os
import bisect 
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

M = 998244353 

pow2 = [1]
for _ in range(300001):  pow2.append(pow2[-1]*2%M)
pow3 = [1]
for _ in range(300001):  pow3.append(pow3[-1]*3%M)



def main(t):



    n = int(input())
    segs = []



    m = 0
    accu = 0
    for _ in range(n):
        l,r = map(int,input().split())
        segs.append([l,r])
        accu += r - l + 1
        m = max(m,r)


    lastappear = [-1]*(m+1)

    rest = [i for i in range(m+1)]


    for i in range(n-1,-1,-1):
        [l,r] = segs[i]
       
        locl = bisect.bisect_left(rest,l)
        locr = bisect.bisect(rest,r)
      
     

        for j in range(locl,locr):
            if lastappear[rest[j]] < 0: lastappear[rest[j]] = i

        if locr - locl > 30:
            rest[locl:locr] = []



    ans = 0
    for j in range(m+1):
        if lastappear[j]<0: continue 
        if lastappear[j]==0:  base = 1
        else:   base = 2*pow3[ lastappear[j]-1 ]              base = base * pow2[ n-1-lastappear[j]] % M   
        ans = (ans + base)%M 

        
        

    print(ans)






















T = 1 t = 1
while t<=T:
    main(t)
    t += 1